Many cryptographic algorithms are based on modular exponentiation calculations of the type m≡cd (mod n) , where c and m can correspond to data of various kinds (plaintext and ciphertext messages, signatures, message digests, authentication codes, etc.) and where d and n cat correspond to elements of public or private keys for operating upon that data. The modulus n is usually the product of two very large primes p and q that are kept secret. The RSA algorithm is one example of an encryption system (and related digital signature scheme) that uses modular exponentiation. The Diffie-Hellman key agreement protocol is another.
In the RSA algorithm, a public key {e, n} and a corresponding private key {d, p, q} are provided for encryption and decryption, where d·e≡1 (mod φ(n)), n=p·q, φ(n)=(p-1) (q-1), and where integer e and φ(n) are co-prime. Alternatively, a function λ(n)=LCM(p-1,q-1) is often used in place of the original φ (n). (RSA PKCS#1 v.2.1) For encryption a ciphertext c may be obtained from a plaintext message m using the public key {e, n} according to the relation c=me (mod n). The public key exponent e is usually a small value (e.g., 3, 5, 35, or 216+1=65537) chosen for ease and speed of encryption. For decryption, the plaintext message m may be recovered from the ciphertext c using the private key {d, p, q} according to the relation m≡cd (mod (p·q)).
The Chinese Remainder Theorem (CRT) is often used to speed the modular exponentiation calculations involved in the decryption, since the otherwise secret prime factors p and q are known to the user. That theorem generally states that given a set of simultaneous congruences x≡ai (mod ni), for i=1 to r, and for which the moduli ni are pairwise relatively prime, the solution is x≡[Σi ai·bi (N/ni)] (mod N), where N=ni·n2·−nr and the bi are determined from bi (N/ni)≡1 (mod ni). For two relatively prime positive integers p and q and two integers a and b (i.e., the case r=2), there exists an integer m uniquely determined modulo p·q, such that m≡a (mod p)≡b (mod q). That is, for GCD (p, q)=1, every pair of residue classes modulo p and q corresponds to a simple residue class modulo p·q. The solution finds m≡[a·(q−1 mod p)·q+b·(p−1 mod q)·p] (mod p·g). A modular inverse of an integer x−1 modulo z is defined such that x·x−1≡1 (mod z). For a prime modulus, every nonzero integer not a multiple of the modulus has an inverse.)
CRT implementation of the RSA algorithm calculates the modular exponentiation m:=cd (mod (p·q)) as follows. First define a pair of private key derived exponents as d1:=d (mod (p-1)) and d2:=d (mod (q-1)). Then, calculate m1:=cd1 (mod p) and m2:=cd2 (mod q).
Finally, m=CRT(m1, m2):=m1+p·{[(m2−m1)·R] (mod q)}, where R≡p−1 (mod q).
That last formula of the CRT implementation, namely m=CRT(m1,m2), has many variants. Three examples of these variants are:
CRT2 (m1,m2):=(m1·R1·q+m2·R2·p) (mod p·q), where R1≡q−1 (mod p) and R2≡p−1 (mod q);
CRT3(m1,m2):={[(m1·R1)(mod p)]·q+[(m2·R2) (mod q)]·p]} (mod p·q), where again R1≡q−1 (mod p) and R2≡p−1 (mod q); and
CRT4 (m1,m2):=(q·{[(m1-m2)·R4] (mod p)}+m2) (mod p·g), where R4≡p−1 (mod q).
Variant CRT implementations perform the modular exponentiation calculation in ways designed to thwart cryptanalysis, especially in the context of tokens (e.g., smart cards) where an attacker has access to the hardware carrying out the cryptographic computations. An attacker may employ noninvasive measurement and timing analysis of electromagnetic emissions, power consumption, or other accessible parameters of a device during computational processes in order to extract useful information regarding the private keys. The variant implementations typically employ pseudo-random variables at various stages of the cryptographic algorithm in order to mask the underlying mathematical operations without affecting the final result.
For example, in CRT implementations of modular exponentiation, some variants transform the message variable m or its CRT components, m1 and m2, by multiplying with a random value at some early stage in the computational process then at a later stage divide the message variable by that same random value or by a related value derived from it to obtain the true result. Other variants may transform the private key exponent d or its CRT components, d1 and d2, by adding a random multiple of (p-1) or (q-1) to obtain another (random) member of the congruence class for that private key component. The private key exponent d could likewise be reduced to transformed CRT components, d1′ and d2′, using moduli that are corresponding random multiples of (p-1) and (q-1), respectively. In all these cases, the design of the transformations are chosen to obtain a true final result, while randomly varying the intermediate calculations in a manner that take advantage of equivalences in congruence arithmetic. Unfortunately, many of these variants can be quite complex and computationally intense.